class Solution {
public:
    int cnt = 0;
    int n;
    void dfs(vector<int>& v, int i, int sum, int target)
    {
        if (i == n)
        {
            if (target == sum)cnt++;
            return;
        }
        dfs(v, i + 1, sum + v[i], target);
        dfs(v, i + 1, sum - v[i], target);
    }
    int findTargetSumWays(vector<int>& nums, int target)
    {
        n = nums.size();
        dfs(nums, 0, 0, target);
        return cnt;
    }
};